package Offer141;

import java.util.HashSet;
import java.util.Set;

/**
 * 环形链表
 * 给定一个链表，判断链表中是否有环
 * @author 23737
 * @time 2021.11.03
 */
public class Test {
    public static void main(String[] args) {

    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

class Solution {
    /**
     * 双指针
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        ListNode p1 = head;
        ListNode p2 = head;
        while(p2!=null && p2.next!=null){
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2){
                return true;
            }
        }
        return false;
    }

    /**
     * hashset
     * @param head
     * @return
     */
    public boolean hasCycle2(ListNode head) {
        ListNode pre = head;
        Set<ListNode> set = new HashSet<>();
        while(pre != null){
            if (set.contains(pre)) return true;
            set.add(pre);
            pre = pre.next;
        }
        return false;
    }
}
